package leetcode.code;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution496 implements IDebug {

	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		Stack<Integer> s = new Stack<>(); // 单调栈
		Map<Integer, Integer> hash = new HashMap<>();
		for (int num : nums2) {
			while (!s.isEmpty() && s.peek() < num) { // 大弹小 , 右侧最近大
				hash.put(s.pop(), num);// 记录
			}
			s.add(num);// 小压大
		}
		for (int i = 0; i < nums1.length; i++) {
			nums1[i] = hash.getOrDefault(nums1[i], -1);// 没有则 -1
		}
		return nums1;
	}

	@Override
	public void debug1() {
		String str1 = "[4,1,2]";
		int[] nums1 = HelpDebug.str2array3(str1);
		String str2 = "[1,3,4,2]";
		int[] nums2 = HelpDebug.str2array3(str2);
		String str3 = "[-1,3,-1]";
		int[] e = HelpDebug.str2array3(str3);
		int[] r = this.nextGreaterElement(nums1, nums2);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str1 = "[2,4]";
		int[] nums1 = HelpDebug.str2array3(str1);
		String str2 = "[1,2,3,4]";
		int[] nums2 = HelpDebug.str2array3(str2);
		String str3 = "[3,-1]";
		int[] e = HelpDebug.str2array3(str3);
		int[] r = this.nextGreaterElement(nums1, nums2);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution496 so = new Solution496();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
